package com.maltys.greedy;

import java.util.Arrays;

/**
 * @author malty
 * @link <a href="https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/">用最少数量的箭引爆气球</a>
 */
public class MinArrows2BurstBalloons {
    public static void main(String[] args) {
        MinArrows2BurstBalloons minArrows2BurstBalloons = new MinArrows2BurstBalloons();
        int cnt = minArrows2BurstBalloons.eraseOverlapIntervals(new int[][]{{2, 3}, {2, 3}});
        System.out.println(cnt);
    }

    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? a[1] - b[1] : a[0] - b[0]);
        int cnt = 0;
        int minRight = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < minRight) {
                minRight = Math.min(intervals[i-1][1], intervals[i][1]);
            } else {
                cnt++;
            }
        }
        return cnt + 1;
    }
}
